"""
题目：实现一个函数，在单链表的指定索引位置插入一个新节点（索引从0开始）。
"""


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val  # 节点值
        self.next = next  # 指向下一节点的指针


def insert_at_index(head, tagetIndex, targetValue):
    # 创建新节点
    new_node = ListNode(targetValue)
    # 特殊情况：插入到头部（索引0）
    if tagetIndex == 0:
        new_node.next = head  # 新节点指向原头节点
        return new_node  # 新节点成为新头节点 到此结束 后面的节点都不用动
    # 遍历找到索引位置的前一个节点
    current = head
    current_index = 0
    # 循环直到找到目标位置的前一个节点或到达链表末尾
    while current and current_index < tagetIndex - 1:
        current = current.next  # 移动到下一个节点
        current_index += 1  # 更新当前索引 继续往后查找
    # 如果索引超出链表长度，无法插入
    if not current:
        return head  # 直接返回原链表
    # 插入新节点
    new_node.next = current.next  # 新节点指向当前节点的下一个节点
    current.next = new_node  # 当前节点指向新节点
    return head  # 返回头节点（可能未改变）


#根据传递过来的参数值 创建链表和遍历链表
def create_linked_list(arr):
    if not arr:
        return None
    head = ListNode(arr[0])
    current = head
    for val in arr[1:]:
        current.next = ListNode(val)
        current = current.next
    return head


def traverse_linked_list(head):
    result = []
    current = head
    while current:
        result.append(current.val)
        current = current.next
    return result


# 测试
head = create_linked_list([1, 2, 3, 4])
head = insert_at_index(head, 2, 99)  # 在索引2位置插入99
print(traverse_linked_list(head))  # 输出: [1, 2, 99, 3, 4]
